#include "stdafx.h"
#include "BinaryTree.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#endif

// ------- Calculate BinTree---------------------------
//  
BinTreeNode* BinTreeOp::locateNode(BinTreeNode* pRoot, string name)
{
    if (pRoot == NULL) 
        return NULL;
    else if (!pRoot->sName.compare(name))
    {
        return pRoot;
    }
    else
    {
        BinTreeNode* pNode = NULL;
        pNode = locateNode(pRoot->plChild, name);
        if (pNode)
        {
            return pNode;
        }
        else
        {
            return locateNode(pRoot->prChild, name);
        }
    }
}

int BinTreeOp::getNodeCout(BinTreeNode* pRoot)
{
    if (pRoot == NULL)
    {
        return 0;
    }

    return(getNodeCout(pRoot->plChild) + getNodeCout(pRoot->prChild) + 1);
}

bool BinTreeOp::isEqual(BinTreeNode* pTree1, BinTreeNode* pTree2)
{
    bool bEqual = false;
    if (pTree1 == NULL && pTree2 == NULL)
    {
        return true;
    }
    else if (pTree1 != NULL && pTree2 != NULL)
    {
        if (!pTree1->sName.compare(pTree2->sName))
        {
            if (isEqual(pTree1->plChild, pTree2->plChild))
            {
                bEqual = isEqual(pTree1->prChild, pTree2->prChild);
            }
        }
    }

    return bEqual;
}

//------------------------Recursive method-----------------------
// Front
void BinTreeOp::TLR(BinTreeNodePtr pRoot)
{
    if (pRoot == NULL)
    {
        return;
    }

    std::cout << pRoot->sName.c_str();

    TLR(pRoot->plChild);

    TLR(pRoot->prChild);
}

// Middle
void BinTreeOp::LTR(BinTreeNodePtr pRoot)
{
    if (pRoot == NULL)
    {
        return;
    }

    // left
    LTR(pRoot->plChild);

    // root
    std::cout << pRoot->sName.c_str();

    // right
    LTR(pRoot->prChild);
}

// Back
void BinTreeOp::LRT(BinTreeNodePtr pRoot)
{
    if (pRoot == NULL)
    {
        return;
    }

    // left
    LRT(pRoot->plChild);

    // right
    LRT(pRoot->prChild);

    // root
    std::cout << pRoot->sName.c_str();
}

//-------------------Non-recursive methods----------------------------
void BinTreeOp::TLR_NoRecursive(BinTreeNode* pRoot)
{
    seqstack seq;

    while (pRoot || seq.top != -1)
    {
        while (NULL != pRoot)
        {
            std::cout << pRoot->sName.c_str();
            seq.push(pRoot);
            pRoot = pRoot->plChild;
        }
        if (seq.top > -1)
        {
            BinTreeNodePtr pNode = seq.pop();
            pRoot = pNode->prChild;   
        }
    }
}

void BinTreeOp::LTR_NoRecursive(BinTreeNode* pRoot)
{
    seqstack seq;

    while (pRoot || seq.top != -1)
    {
        while (NULL != pRoot)
        {
            seq.push(pRoot);
            pRoot = pRoot->plChild;
        }
        if (seq.top > -1)
        {
            BinTreeNodePtr pNode = seq.pop();
            std::cout << pNode->sName.c_str();
            pRoot = pNode->prChild;   
        }
    }
}

void BinTreeOp::LRT_NoRecursive(BinTreeNode* pRoot)
{
    seqstack seq;
    while (pRoot || seq.top != -1)
    {
        while (NULL != pRoot)
        {
            seq.push(pRoot);
            seq.changeTag(false);
            pRoot = pRoot->plChild;
        }

        while (seq.top > -1 && seq.tag[seq.top])
        {
            pRoot = seq.pop();
            std::cout << pRoot->sName.c_str();
        }

        if (seq.top > -1)
        {
            BinTreeNode* pNode = seq.node[seq.top];
            seq.changeTag(true);
            pRoot = pNode->prChild;
        }
        else
        {
            pRoot = NULL;
        }
    }
}